package chalmers.edu.jacobla_anerud.lab1_3;

public final class MaxSum {
	static public int seqStart = 0;
	static public int seqEnd = -1;
	/**
	* contiguous subsequence sum algorithm.
	* seqStart and seqEnd represent the actual best sequence.
	* Version 1-------- 10,3,4,6,3,13,23,8,2,10
	*/
	public static int maxSubSum1( int[] a ) {
		int maxSum = 0;
		for( int i = 0; i < a.length; i++ ){
			for( int j = i; j < a.length; j++ ) {
				int thisSum = 0;
				for( int k = i; k <= j; k++ ) {
					thisSum += a[k];
				}
				if( thisSum > maxSum ) {
					maxSum   = thisSum;
					seqStart = i;
					seqEnd   = j;
				}
			}
		}
		return maxSum;
	}
	// Version 2
	public static int maxSubSum2( int[] a ) {
		int maxSum = 0;
		for( int i = 0; i < a.length; i++ ) {
			int thisSum = 0;
			for( int j = i; j < a.length; j++ ) {
				thisSum += a[j];
				if( thisSum > maxSum ) {
					maxSum = thisSum;
					seqStart = i;
					seqEnd   = j;
				}
			}
		}
		return maxSum;
	}
	// Version 3
	public static int maxSubSum3( int[] a ) {
		int maxSum  = 0;
		int thisSum = 0;
		for( int i = 0, j = 0; j < a.length; j++ ) {
			thisSum += a[j];
			if( thisSum > maxSum ) {
				maxSum = thisSum;
				seqStart = i;
				seqEnd   = j;
			}else if( thisSum < 0 ) {
				i = j + 1;
				thisSum = 0;
			}
		}
		return maxSum;
	}
}
